package com.Questions.DFS;


import java.util.*;

/**
 * 有向无环图中一个节点的所有祖先
 */
public class leetcode2192 {
    // 官解：拓扑排序
    // 取并集的过程 等价于在拓扑排序的过程中使用每一个结点的祖先
    // 集合更新每个结点所有子节点的祖先集合
    // 不断选取入度为0（这说明该点所有的祖先结点已经更新完成）
    // 并且更新该节点通过出边相邻的结点

    // 借此 加深对拓扑排序的理解
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        // n结点数目 0- n-1
        // edge 表示图的边
        // 返回第i个节点的所有祖先这个结点的所有祖先按照升序排序
        Set<Integer>[] anc=new Set[n];// 存储每一个结点祖先结点的辅助数组
        for(int i=0;i<n;++i){
            anc[i]=new HashSet<Integer>();
        }// 看来还是需要理解java的引用
        List<Integer>[] e=new List[n];// 邻接表(拓扑排序需要得到每一个结点的入度，如果直接使用临界矩阵可能需要双循环 时间复杂度可能变高)
        for(int i=0;i<n;++i){
            e[i]=new ArrayList<Integer>();
        }
        int[] indeg=new int[n];// 入度表
        // 预处理
        for(int[] edge:edges){// java中将未初始化的结点赋值为0
            e[edge[0]].add(edge[1]);// 将数组中表示的每一个边都存入邻接表
            ++indeg[edge[1]];//终点的入度加一
        }
        // 广度优先搜索求解拓扑排序
        Queue<Integer> q=new ArrayDeque<>();
        for(int i=0;i<n;++i){// 首先将入度为0的结点入队
            if(indeg[i]==0){
                q.offer(i);
            }
        }
        while (!q.isEmpty()){
            int u=q.poll();// 删除队尾元素并返回(u是在队列中得到的 其入度自然为0)
            for(int v:e[u]){//每一个u结点指向的结点v
                anc[v].add(u);// u结点更新已经完成 将u加入到u指向的每一个结点的祖先集合中
                for(int i:anc[u]){
                    anc[v].add(i);// 将u本身的祖先结点加入到v当中
                }
                --indeg[v];// v结点的入度减一
                if(indeg[v]==0){// 如果入度为0 则将该节点加入到 队列中
                    q.offer(v);
                }
            }
        }
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        for(int i=0;i<n;++i){// 对于结点i 将它的祖先集合连接到数组中 并且进行排序
            res.add(new ArrayList<Integer>());
            for(int j:anc[i]){
                res.get(i).add(j);
            }
            Collections.sort(res.get(i));
        }
        return res;
    }
}

